『A comprehensive study of Convergent and Commutative Replicated Data Types』
Abstract
Eventual consistency は、同期機構なしで、レプリカの状態が収束するという保証を目的とする
既存の eventual consistency に関する手法はアドホックで間違いが起きやすいものだった
原理的な手法を研究した: eventual consistency を保証するのに十分なシンプルで形式的な条件の上で、データ型の設計方法
このようなデータ型を収束複製データ型 (Convergent Replicated Data Types) あるいは可換複製データ型 (Commutative Replicated Data Types)、略して CRDTs と名付けた
この論文では、状態ベースと操作ベースでの非同期オブジェクトレプリケーションについて形式化し、各ケースについて十分条件を与える
また、いくつかの CRDTs の例も説明する。例えば add と remove があるようなコンテナの型や、グラフのような複雑な型、DAG、そして列などである
非自明な CRDTs の実装に必要な性質についても議論する
Introduction
レプリケーション
いろいろ研究されてきた
主にグローバルな全順序づけに関するもの (障害とかあっても)
でもパフォーマンスとスケーラビリティに問題があった
結果整合性 (eventual consistency) と楽観的レプリケーション (optimistic replication)
各レプリカには個別に操作がされる
レプリカの操作は非同期的に他のレプリカに送られる
順序は変わりうる
裏にある合意アルゴリズムが、衝突するような更新をよしなに (reconcile) する
この手法は、ネットワーク分断があっても大丈夫
合意アルゴリズムがクリティカルパスから外れるため、パフォーマンスも良い
弱い一貫性でもいいアプリケーションもたくさんある
でも、衝突をよしなにする (reconciliation) のは複雑だし、正しく実装・設計するのは難しいし、アドホックでもある
CRDT
この論文では、結果整合性のシンプルで理論的にしっかりした手法を提案する
convergent or commutative replicated data type (CRDT)
簡単な例: レプリケートされたカウンタ
increment と decrement が可換であるため、収束する
他のノードとの同期機構がいらないので、更新は即座に実行できて、ネットワークレイテンシやコネクションの切断やクラッシュも気にしなくていい
英単語
converge: 収束する
commute: 可換
reconcile: 調和させる